home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume2 / bgrep < prev    next >
Encoding:
Internet Message Format  |  1986-11-30  |  12.1 KB
  1. From: Arnold Robbins <linus!gatech!arnold>
  2. Subject: Boyer-Moore based fgrep like program
  3. Newsgroups: mod.sources
  4. Approved: john@genrad.UUCP
  5.  
  6. Mod.sources:  Volume 2, Issue 3
  7. Submitted by: Arnold Robbins <linus!gatech!arnold>
  8.  
  9.  
  10. The following program may be of some use to people out there.  In the usual
  11. case of looking for a single string, it is 10% to 20% faster than fgrep.
  12.  
  13. There is no makefile, since everything is in a single source file.  Just
  14. compile with "cc -O bgrep.c -o bgrep".
  15.  
  16. Enjoy,
  17.  
  18. Arnold Robbins
  19. arnold@gatech.{UUCP, CSNET}
  20. -------------- cut here ------------------------
  21. #!/bin/sh
  22. # This is a shell archive, meaning:
  23. # 1. Remove everything above the #!/bin/sh line.
  24. # 2. Save the resulting text in a file.
  25. # 3. Execute the file with /bin/sh (not csh) to create the files:
  26. #    bgrep.c
  27. #    bgrep.1
  28. # This archive created: Mon Jul  1 10:52:37 1985
  29. # By:    Arnold Robbins (Pr1mebusters!)
  30. export PATH; PATH=/bin:$PATH
  31. echo shar: extracting "'bgrep.c'" '(8635 characters)'
  32. if test -f 'bgrep.c'
  33. then
  34.     echo shar: over-writing existing file "'bgrep.c'"
  35. fi
  36. cat << \SHAR_EOF > 'bgrep.c'
  37. /* bgrep --- grep using Boyer-Moore pattern matcher */
  38.  
  39. /*
  40.  * All the wrapper code (argument and file handling, printing, etc.) by
  41.  * Arnold Robbins, gatech!arnold
  42.  *
  43.  * Boyer-Moore pattern matching, coded by Roy Mongiovi, gatech!gitpyr!roy
  44.  * and edited some by Arnold Robbins.
  45.  *
  46.  * No warranty of suitability for any purpose, either expressed
  47.  * or implied, is made.
  48.  */
  49.  
  50. #include <stdio.h>
  51. #include <ctype.h>
  52.  
  53. #define TRUE    1
  54. #define FALSE    0
  55.  
  56. #define MAXPATS    120        /* (arbitrary maximum number of patterns */
  57. #define MAXLINE    (256 + 1)
  58.  
  59. /*
  60.  * command line options
  61.  */
  62.  
  63. int Allbut = FALSE;        /* print lines that don't match pattern */
  64. int Exact = FALSE;        /* only print lines that match exactly */
  65. int Countlines = FALSE;        /* only print a count of matching lines */
  66. int Listnames = FALSE;        /* only list file names that match */
  67. int Numberlines = FALSE;    /* print relative line number */
  68. int Silent = FALSE;        /* don't print anything, just exit */
  69. int Monocase = FALSE;        /* ignore case distinctions */
  70.  
  71. /*
  72.  * variables
  73.  */
  74.  
  75. long Curline = 0;        /* current file input line */
  76. long Lines_matched = 0;        /* how many lines matched the pattern */
  77.  
  78. int Lotsafiles = FALSE;        /* are there more than one file? */
  79. int Pat_length[MAXPATS];    /* length of pattern */
  80. int Line_length = 0;        /* length of line */
  81. int Couldnt_open_files = FALSE;    /* one or more files could not be opened */
  82. int Exit_val = 0;        /* return code status */
  83. int Curpat = 0;            /* current pattern comparing against */
  84. int Numpats = 0;        /* total number of patterns */
  85.  
  86. char Inbuf[MAXLINE];        /* input buffer */
  87. char Pattern[MAXPATS][MAXLINE];    /* pattern to be matched; init = NULs */
  88. char *Program = NULL;        /* program name */
  89.  
  90. int Argc;            /* make argc and argv global */
  91. char **Argv;
  92.  
  93. extern char *basename();    /* leaf file of a pathname */
  94.  
  95. main (argc, argv, envp)
  96. int argc;
  97. char **argv, **envp;
  98. {
  99.     register int i, j;
  100.     char *index();
  101.  
  102.     Program = basename (argv[0]);
  103.     Argc = argc;
  104.     Argv = argv;
  105.  
  106.     parse_args ();        /* deal with command line */
  107.  
  108.     if (Pattern[0][0] == '\0')    /* not from -f or -e */
  109.     {
  110.         if (Argv[0] == NULL)    /* no string given */
  111.             usage ();
  112.         setpats (Argv[0]);
  113.         Argc--;
  114.         Argv++;
  115.     }
  116.  
  117.     for (Curpat = 0; Curpat <= Numpats; Curpat++)
  118.     {
  119.         if (Monocase)
  120.             mapdown (Pattern[Curpat]);
  121.  
  122.         Pat_length[Curpat] = strlen (Pattern[Curpat]);
  123.         initialize ();        /* set up necessary tables */
  124.     }
  125.  
  126.     Lotsafiles = (Argc > 1);    /* more than one file left */
  127.  
  128.     if (Argc == 0)        /* search stdin */
  129.         process ("-");
  130.     else
  131.         for (i = 0; Argv[i] != NULL; i++)
  132.             process (Argv[i]);
  133.     
  134.     if (! Silent && Countlines)
  135.         printf ("%ld\n", Lines_matched);
  136.  
  137.     if (Lines_matched == 0)
  138.         exit (1);
  139.     else if (Couldnt_open_files)
  140.         exit (2);
  141.     else
  142.         exit (0);
  143. }
  144.  
  145. /* process --- start doing the work on each file */
  146.  
  147. process (infile)
  148. register char *infile;
  149. {
  150.     FILE *fp;
  151.     int c;
  152.     int success;
  153.     long prev_lines_matched = Lines_matched;    /* save count */
  154.  
  155.     Curline = 0;    /* reset for each file */
  156.  
  157.     if (infile[0] == '-' && infile[1] == '\0')
  158.         fp = stdin;
  159.     else if ((fp = fopen (infile, "r")) == NULL)
  160.     {
  161.         Couldnt_open_files = TRUE;
  162.         perror (infile);
  163.         return;
  164.     }
  165.  
  166.     while (fgets (Inbuf, sizeof Inbuf, fp) != NULL)
  167.     {
  168.         Curline++;
  169.         if (Monocase)
  170.             mapdown (Inbuf);
  171.         Line_length = strlen (Inbuf);
  172.  
  173.         /* first, throw away rest of a truncated input line */
  174.         if (Inbuf[Line_length - 1] != '\n')
  175.             while ((c = getc (fp)) != '\n')
  176.                 ;
  177.         else
  178.             Inbuf[--Line_length] = '\0';
  179.             /* newline is there, nuke it */
  180.  
  181.         for (Curpat = 0; Curpat <= Numpats; Curpat++)
  182.         {
  183.             if (success = match ())
  184.                 Lines_matched++;
  185.             /* do any necessary output */
  186.             if (! Silent && ! Countlines && ! Listnames &&
  187.                 ((success != FALSE) ^ (Allbut != FALSE)))
  188.                 /* either success, or Allbut, but not both,
  189.                    and not neither */
  190.             {
  191.                 if (Lotsafiles)
  192.                     printf ("%s: ", infile);
  193.                 if (Numberlines)
  194.                     printf ("%ld: ", Curline);
  195.                 printf ("%s\n", Inbuf);
  196.             }
  197.         }
  198.     }
  199.  
  200.     fclose (fp);
  201.     if (! Silent && Listnames && prev_lines_matched < Lines_matched)
  202.         printf ("%s\n", infile);
  203. }
  204.  
  205. /* parse_args --- check out command line arguments */
  206.  
  207. parse_args ()
  208. {
  209.     register int i,j;
  210.  
  211.     if (Argc == 1)
  212.         usage ();
  213.  
  214.     for (Argc--, Argv++; Argv[0] != NULL && Argv[0][0] == '-'; Argc--, Argv++)
  215.     {
  216.         int cheat = FALSE;
  217.  
  218.         for (j = 1; Argv[0][j] != '\0'; j++)
  219.         {
  220.             switch (Argv[0][j]) {
  221.             case 'c':
  222.                 Countlines = TRUE;
  223.                 break;
  224.  
  225.             case 'e':
  226.                 strcpy (Pattern[0], Argv[1]);
  227.                 Pattern[0][sizeof Pattern[0] - 1] = '\0';
  228.                 cheat = TRUE;
  229.                 continue;
  230.  
  231.             case 'f':
  232.                 patfromfile (Argv[1]);
  233.                 cheat = TRUE;
  234.                 continue;
  235.  
  236.             case 'i':
  237.             case 'y':
  238.                 Monocase = TRUE;
  239.                 break;
  240.  
  241.             case 'l':
  242.                 Listnames = TRUE;
  243.                 break;
  244.  
  245.             case 'n':
  246.                 Numberlines = TRUE;
  247.                 break;
  248.  
  249.             case 's':
  250.                 Silent = TRUE;
  251.                 break;
  252.  
  253.             case 'v':
  254.                 Allbut = TRUE;
  255.                 break;
  256.  
  257.             case 'x':
  258.                 Exact = TRUE;
  259.                 break;
  260.  
  261.             default:
  262.                 usage ();
  263.                 break;
  264.             }
  265.         }
  266.         if (cheat)
  267.         {
  268.             cheat = FALSE;
  269.             Argc--;
  270.             Argv++;
  271.             /* boy is this stuff a kludge! */
  272.         }
  273.     }
  274.  
  275.     /* check for argument conflicts */
  276.     if (
  277.         (Silent &&
  278.             (Allbut || Exact || Countlines || Listnames ||
  279.                 Numberlines))
  280.         ||
  281.         (Allbut && Exact)
  282.         ||
  283.         (Countlines && Listnames)
  284.     )
  285.     {
  286.         fprintf (stderr, "%s: argument conflict -- see the man page\n",
  287.             Program);
  288.         usage ();    /* will exit */
  289.     }
  290. }
  291.  
  292. /* mapdown --- remove case distinctions in a string */
  293.  
  294. mapdown (str)
  295. register char *str;
  296. {
  297.     register int i;
  298.  
  299.     for (i = 0; str[i] != '\0'; i++)
  300.         if (isupper (str[i]))
  301.             str[i] = tolower (str[i]);
  302. }
  303.  
  304. /* return basename part of a pathname, if '/'s are present */
  305.  
  306. char *basename (str)
  307. register char *str;
  308. {
  309.     register int i = 0;
  310.     register int j = 0;
  311.  
  312.     for (; str[i] != '\0'; i++)
  313.         if (str[i] == '/')
  314.             j = i;
  315.     
  316.     if (j != 0)
  317.         return (& str[++j]);
  318.     else
  319.         return (str);
  320. }
  321.  
  322. /* usage --- print usage message and die */
  323.  
  324. usage ()
  325. {
  326.     fprintf (stderr, "usage: %s [-vxclnisef] [string] [files]\n",
  327.             Program);
  328.     exit (2);
  329. }
  330.  
  331. /* index --- do index by hand so it'll work on any Unix */
  332.  
  333. char *index (str, c)
  334. char *str, c;
  335. {
  336.     for (; *str; str++)
  337.         if (*str == c)
  338.             return (str);
  339.     
  340.     return (NULL);
  341. }
  342.  
  343. /* patfromfile --- retrieve the pattern from the named file */
  344.  
  345. patfromfile (infile)
  346. char *infile;
  347. {
  348.     register int i, j;
  349.     register FILE *fp;
  350.     register int c;
  351.  
  352.     if ((fp = fopen (infile, "r")) == NULL ||
  353.             (c = getc (fp)) == EOF)
  354.     {
  355.         perror (infile);    /* be like standard grep */
  356.         exit (2);
  357.     }
  358.     else
  359.         ungetc (c, fp);
  360.  
  361.     for (i = 0; fgets (Pattern[i], MAXLINE, fp) != NULL; i++)
  362.     {
  363.         if (i >= 120)
  364.         {
  365.             fprintf (stderr, "%s: Only %d strings allowed\n",
  366.                 Program, MAXPATS);
  367.             exit (2);
  368.         }
  369.         j = strlen (Pattern[i]);
  370.         if (Pattern[i][j - 1] == '\n')
  371.             Pattern[i][--j] = '\0';
  372.     }
  373.     Numpats = i - 1;
  374.  
  375.     fclose (fp);
  376. }
  377.  
  378. /* setpats --- set up the patterns from a string */
  379.  
  380. setpats (str)
  381. register char *str;
  382. {
  383.     register int i, j;
  384.  
  385.     while (*str == '\n' || *str == '\r')
  386.         str++;
  387.  
  388.     for (i = j = 0; *str; str++)
  389.     {
  390.         if (*str == '\n')
  391.         {
  392.             Pattern[i][j] = '\0';
  393.             j = 0;
  394.             i++;
  395.         }
  396.         else
  397.             Pattern[i][j++] = *str;
  398.     }
  399.     Numpats = i;
  400. }
  401.  
  402. /* begin magic stuff for Boyer-Moore pattern matching */
  403.  
  404. int D1[MAXPATS][128];
  405. int D2[MAXPATS][128];
  406.  
  407. int F[MAXPATS][128];
  408.  
  409. initialize ()
  410. {
  411.     register int i, t;
  412.  
  413.     for (i = 0; i < 128; i++)
  414.         D1[Curpat][i] = Pat_length[Curpat];
  415.     
  416.     for (i = 0; i < Pat_length[Curpat]; i++)
  417.         D1[Curpat][Pattern[Curpat][i]] = Pat_length[Curpat] - i - 1;
  418.     
  419.     for (i = 0; i < Pat_length[Curpat]; i++)
  420.         D2[Curpat][i] = (Pat_length[Curpat] << 1) - i - 1;
  421.     
  422.     for (i = (t = Pat_length[Curpat]) - 1; i >= 0; i--, t--)
  423.         for (F[Curpat][i] = t; t < Pat_length[Curpat]
  424.             && Pattern[Curpat][i] != Pattern[Curpat][t];
  425.                             t = F[Curpat][t])
  426.             if (Pat_length[Curpat] - i - 1 < D2[Curpat][t])
  427.                 D2[Curpat][t] = Pat_length[Curpat] - i - 1;
  428.  
  429.     for (i = 0; i <= t; i++)
  430.         if (Pat_length[Curpat] + t - i < D2[Curpat][i])
  431.             D2[Curpat][i] = Pat_length[Curpat] + t - i;
  432. }
  433.  
  434. /* match --- do Boyer-Moore pattern search on input buffer */
  435.  
  436. match ()
  437. {
  438.     register int i, j;
  439.  
  440.     if (Exact && Pat_length[Curpat] != Line_length)
  441.         return FALSE;
  442.  
  443.     i = Pat_length[Curpat] - 1;
  444.  
  445.     while (i < Line_length)
  446.     {
  447.         j = Pat_length[Curpat] - 1;
  448.         while (j >= 0)
  449.         {
  450.             if (Inbuf[i] == Pattern[Curpat][j])
  451.                 i--, j--;
  452.             else
  453.                 break;
  454.         }
  455.  
  456.         if (j < 0)
  457.         {
  458.             /* found a match */
  459.             return TRUE;
  460.             /*
  461.              * note: if we were going to seach for further matches
  462.              * on the input line, we would do this:
  463.              *
  464.              * i += Pat_length[Curpat] + 1;
  465.              *
  466.              * which shifts right by Pat_length[Curpat] + 1 places
  467.              */
  468.         }
  469.         else
  470.         {
  471.             j = (D1[Curpat][Inbuf[i]] >= D2[Curpat][j]) ?
  472.                 D1[Curpat][Inbuf[i]]
  473.             :
  474.                 D2[Curpat][j];
  475.             i += j;
  476.             /* shift right by j places */
  477.         }
  478.     }
  479.  
  480.     return FALSE;
  481. }
  482. SHAR_EOF
  483. echo shar: extracting "'bgrep.1'" '(2419 characters)'
  484. if test -f 'bgrep.1'
  485. then
  486.     echo shar: over-writing existing file "'bgrep.1'"
  487. fi
  488. cat << \SHAR_EOF > 'bgrep.1'
  489. .TH BGREP 1 "Georgia Tech"
  490. .SH NAME
  491. bgrep \- search a file for one or more simple strings
  492. .SH SYNOPSIS
  493. .B bgrep
  494. [ options ] string-list [ files ]
  495. .SH DESCRIPTION
  496. .I Bgrep
  497. (Boyer\-Moore grep) is program patterned after
  498. .IR fgrep (1).
  499. It uses the Boyer\-Moore string searching algorithm, which actually gets
  500. faster as the length of the pattern to be searched for increases.
  501. .I Bgrep
  502. searches for plain
  503. .I strings\^
  504. (separated by newlines in the
  505. .I string-list\^
  506. argument),
  507. not regular expressions in the style of
  508. .IR grep .
  509. .PP
  510. The following
  511. .I options
  512. are recognized:
  513. .TP
  514. .B \-v
  515. All lines but those matching are printed.
  516. .TP
  517. .B \-x
  518. (Exact) only lines matched in their entirety are printed.
  519. .TP
  520. .B \-c
  521. Only a count of the matching lines are printed.
  522. This is the total count, across all the input files.
  523. .TP
  524. .BR \-i " or " \-y
  525. Ignore case when trying to match a line.
  526. Both versions of this option are accepted for compatibility with
  527. .I grep
  528. on different versions of Unix.
  529. .TP
  530. .B \-l
  531. Only the names of files with matching lines are printed (once),
  532. separated by newlines.
  533. .TP
  534. .B \-n
  535. Each line is preceded by its relative line number within the file.
  536. .TP
  537. .B \-s
  538. Silent mode:  No output is generated (except error messages).
  539. This is useful for just checking the exit status.
  540. .TP
  541. .BI \-e " string"
  542. Same as a simple
  543. .I string
  544. argument, but useful when the string begins with a \-.
  545. .TP
  546. .BI \-f " file"
  547. The strings to be searched for are read from
  548. .IR file .
  549. .PP
  550. The arguments to the
  551. .BR \-e " and " \-f
  552. options
  553. .I must
  554. be given as separate program arguments, i.e. separated by white space.
  555. .PP
  556. .I Bgrep
  557. catches conflicting arguments (e.g.
  558. .BR \-v " and " \-x )
  559. and complains.
  560. .SH SEE ALSO
  561. .IR ed (1),
  562. .IR sed (1),
  563. .IR grep (1),
  564. .IR sh (1)
  565. .SH DIAGNOSTICS
  566. Exit status 0 if any matches were found, 1 if none, 2 for syntax
  567. errors on the command, or if any files could not be opened (even if
  568. matches were found).
  569. .SH BUGS
  570. Input lines and the strings to be searched for are limited to 256 characters.
  571. Longer input lines are truncated.
  572. .PP
  573. .I Bgrep\^
  574. will not search for any more than 120 different strings.
  575. .PP
  576. Uses the <stdio.h> package, which slows it down some.
  577. Nonetheless, in the usual case,
  578. it is 10% to 20% faster than
  579. .IR fgrep (1).
  580. .SH AUTHORS
  581. Roy Mongiovi (gatech!gitpyr!roy) coded the guts of the Boyer\-Moore algorithm,
  582. while Arnold Robbins (gatech!arnold) wrote the code to do all the rest of
  583. the work, and the man page.
  584. SHAR_EOF
  585. #    End of shell archive
  586. exit 0
  587.  
  588.